<!DOCTYPE HTML PUBLIC "-//IETF//DTD HTML 2.0//EN">
<html><head>
<meta http-equiv="content-type" content="text/html; charset=ISO-8859-1">
<!--Converted with LaTeX2HTML 96.1 (Feb 5, 1996) by Nikos Drakos (nikos@cbl.leeds.ac.uk), CBLU, University of Leeds -->


<title>Testing the CATCHER</title>
<meta name="description" content="Testing the CATCHER">
<meta name="keywords" content="htmlatex">
<meta name="resource-type" content="document">
<meta name="distribution" content="global">
<link rel="STYLESHEET" href="acm-00231_files/htmlatex.css">
</head><body bgcolor="#ffffff" lang="EN">
 <h1><br clear="ALL"><center><table bgcolor="#0060f0"><tbody><tr><td><b><font color="#c0ffff" size="5">&nbsp;<a name="SECTION0001000000000000000000">Testing the CATCHER</a></font>&nbsp;</b></td></tr></tbody></table></center></h1>
<p>
A military contractor for the Department of Defense has just completed a 
series of preliminary tests for a new defensive missile called the CATCHER 
which is capable of intercepting multiple incoming offensive missiles. The 
CATCHER is supposed to be a remarkable defensive missile. It can move forward, 
laterally, and downward at very fast speeds, and it can intercept an offensive 
missile without being damaged. But it does have one major flaw. Although it 
can be fired to reach any initial elevation, it has no power to move higher 
than the last missile that it has intercepted.
</p><p>
</p><p>
The tests which the contractor completed were computer simulations of 
battlefield and hostile attack conditions. Since they were only preliminary, 
the simulations tested only the CATCHER's vertical movement capability. In
each simulation, the CATCHER was fired at a sequence of offensive missiles 
which were incoming at fixed time intervals. The only information available to 
the CATCHER for each incoming missile was its height at the point it could be 
intercepted and where it appeared in the sequence of missiles. Each incoming 
missile for a test run is represented in the sequence only once.
</p><p>
</p><p>
The result of each test is reported as the sequence of incoming missiles and 
the total number of those missiles that are intercepted by the CATCHER in that 
test.
</p><p>
</p><p>
The General Accounting Office wants to be sure that the simulation test 
results submitted by the military contractor are attainable, given the 
constraints of the CATCHER. You must write a program that takes input data 
representing the pattern of incoming missiles for several different tests and 
outputs the maximum numbers of missiles that the CATCHER can intercept for 
those tests. For any incoming missile in a test, the CATCHER is able to 
intercept it if and only if it satisfies one of these two conditions:
</p><p>
</p><dl compact="compact"><dt></dt><dd> The incoming missile is the first missile to be intercepted in this
test.
</dd><dt><strong>-<i>or</i>-</strong>
</dt><dd>
</dd><dt></dt><dd> The missile was fired after the last missile that was intercepted and it
is not higher than the last missile which was intercepted.
<p>
 </p></dd></dl><h2><font color="#0070e8"><a name="SECTION0001001000000000000000">Input</a></font></h2>
<p>
The input data for any test consists of a sequence of one or more non-negative 
integers, all of which are less than or equal to 32,767, representing the 
heights of the incoming missiles (the test pattern). The last number in each 
sequence is <tt>-1</tt>, which signifies the end of data for that particular test and
is not considered to represent a missile height. The end of data for the 
entire input is the number <tt>-1</tt> as the first value in a test; it is not
considered to be a separate test.
</p><p>
</p><h2><font color="#0070e8"><a name="SECTION0001002000000000000000">Output</a></font></h2>
<p>
Output for each test consists of a test number (<tt>Test #1</tt>, <tt>Test #2</tt>, etc.) and
the maximum number of incoming missiles that the CATCHER could possibly 
intercept for the test. That maximum number appears after an identifying 
message. There must be at least one blank line between output for successive 
data sets.
</p><p>
</p><p>
</p><p>
<b>Note:</b> The number of missiles for any given test is not limited. If your
solution is based on an inefficient algorithm, it <b>may not</b> execute in the
allotted time.
</p><p>
</p><h2><font color="#0070e8"><a name="SECTION0001003000000000000000">Sample Input</a></font></h2>
<p>
</p><pre>389
207
155
300
299
170
158
65
-1
23
34
21
-1
-1</pre>
<p>
</p><h2><font color="#0070e8"><a name="SECTION0001004000000000000000">Sample Output</a></font></h2>
<p>
</p><pre>Test #1:
  maximum possible interceptions: 6

Test #2:
  maximum possible interceptions: 2</pre>
<p>
</p></body></html>